﻿#define _CRT_SECURE_NO_WARNINGS 1
/*
【例3】 有 2*n的一个长方形方格，用一个1*2的骨牌铺满方格。

编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
【算法分析】
　（1）面对上述问题，如果思考方法不恰当，要想获得问题的
解答是相当困难的。可以用递推方法归纳出问题解的一般规律。
　（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。
　（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，
再无其他方法，如下左图所示，因此，铺法总数表示为x2=2；
  （4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖
排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在
方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，
再无其他排列方法，因此铺法总数表示为x3=3。
由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。
  （5）推出一般规律：对一般的n，要求xn可以这样来考虑，
若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时
排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少
有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，
这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两
种可能，所以有：
             xn=x(n-1)+x(n-2)   （n>2）
             x1=1
             x2=2
xn=x(n-1)+x(n-2)就是问题求解的递推公式。任给n都可
以从中获得解答。例如n=5，
           x3=x2+x1=3
           x4=x3+x2=5
           x5=x4+x3=8

*/

#include<iostream>
using namespace std;
int main()
{
    int n, i, j, a[101];
    cout << "input n:";//输入骨牌数
    cin >> n;
    a[1] = 1; a[2] = 2;
    cout << "x[1]=" << a[1] << endl;
    cout << "x[2]=" << a[2] << endl;
    for (i = 3; i <= n; i++)//递推过程
    {
        a[i] = a[i - 1] + a[i - 2];
        cout << "x[" << i << "]=" << a[i] << endl;
    }
}



